package com.fr.lintcode;

public class Q633 {

	/**
	 * @param nums: an array containing n + 1 integers which is between 1 and n
	 * @return: the duplicate one https://www.cnblogs.com/grandyang/p/4843654.html
	 */
	// 二分查找
	public int findDuplicate(int[] nums) {
		// write your code here
		if (nums == null || nums.length == 0) {
			return 0;
		}
		int left = 0, right = nums.length;
		while(left < right) {
			int mid = (left + right) / 2;
			int count = 0;
			for(int i : nums) {
				if(mid >= i) {
					count ++;
				}
			}
			if(count <= mid) {
				left = mid + 1;
			}else {
				right = mid;
			}
		}
		return 0;
	}

	// 快慢指针  key = index, value = nums[index]
	public int findDuplicate2(int[] nums) {
		// write your code here
		if (nums == null || nums.length == 0) {
			return 0;
		}
		int slow = 0;
		int fast = 0;
		int t = 0;
		//环 第一次相交
		while(true) {
			slow = nums[slow];
			fast = nums[nums[fast]];
			if(fast == slow) {
				break;
			}
		}
		//环起点
		while (true) {
            slow = nums[slow];
            t = nums[t];
            if (slow == t) break;
        }
        return slow;
	}

}
